class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 状态表示 - 第 i 天买入的最大利润
        int[][] f = new int[n][3];// 第 i 天结束，交易 j 次，处于买入状态的最大利润
        int[][] g = new int[n][3];// 第 i 天卖出，交易 j 次，处于卖出状态的最大利润
        // 初始化
        int INF = 0x3F3F3F3F;
        for(int j = 0; j < 3; j++) {
            f[0][j] = -INF;
            g[0][j] = -INF;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        // 状态转移方程
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= 2; j++){
                // 买入状态
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // 卖出状态
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0)
                    g[i][j] = Math.max(f[i - 1][j - 1] + prices[i], g[i - 1][j]);
            }
        }
        // 返回值
        int ret = 0;
        for(int j = 0; j < 3; j++)
            ret = Math.max(ret, g[n - 1][j]);

        return ret;
    }
}